//判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。 
//
// 
// 数字 1-9 在每一行只能出现一次。 
// 数字 1-9 在每一列只能出现一次。 
// 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 
// 
//
// 
//
// 上图是一个部分填充的有效的数独。 
//
// 数独部分空格内已填入了数字，空白格用 '.' 表示。 
//
// 示例 1: 
//
// 输入:
//[
//  ["5","3",".",".","7",".",".",".","."],
//  ["6",".",".","1","9","5",".",".","."],
//  [".","9","8",".",".",".",".","6","."],
//  ["8",".",".",".","6",".",".",".","3"],
//  ["4",".",".","8",".","3",".",".","1"],
//  ["7",".",".",".","2",".",".",".","6"],
//  [".","6",".",".",".",".","2","8","."],
//  [".",".",".","4","1","9",".",".","5"],
//  [".",".",".",".","8",".",".","7","9"]
//]
//输出: true
// 
//
// 示例 2: 
//
// 输入:
//[
//  ["8","3",".",".","7",".",".",".","."],
//  ["6",".",".","1","9","5",".",".","."],
//  [".","9","8",".",".",".",".","6","."],
//  ["8",".",".",".","6",".",".",".","3"],
//  ["4",".",".","8",".","3",".",".","1"],
//  ["7",".",".",".","2",".",".",".","6"],
//  [".","6",".",".",".",".","2","8","."],
//  [".",".",".","4","1","9",".",".","5"],
//  [".",".",".",".","8",".",".","7","9"]
//]
//输出: false
//解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。
//     但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。 
//
// 说明: 
//
// 
// 一个有效的数独（部分已被填充）不一定是可解的。 
// 只需要根据以上规则，验证已经填入的数字是否有效即可。 
// 给定数独序列只包含数字 1-9 和字符 '.' 。 
// 给定数独永远是 9x9 形式的。 
// 
// Related Topics 哈希表 
// 👍 401 👎 0

package leetcode.editor.cn;

//Java：有效的数独
public class P36ValidSudoku {

    /**
     * 思路：创建三个二维数组，记录每行，每列，每九格出现的字符次数，大于一的话就是false
     *
     *
     * 执行用时： 2 ms , 在所有 Java 提交中击败了 96.43% 的用户 内存消耗： 39.6 MB , 在所有 Java 提交中击败了 81.94% 的用户
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean isValidSudoku(char[][] board) {
            int[][] rows = new int[board.length][board.length];
            int[][] columns = new int[board.length][board.length];
            int[][] nineGrids = new int[board.length][board.length];

            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[i].length; j++) {
                    if ('.' == board[i][j]) {
                        continue;
                    }
                    // 字符1-9 转为对应的数字 0-8
                    int index = board[i][j] - '1';

                    // 第i行
                    if (rows[i][index] > 0) {
                        return false;
                    }
                    rows[i][index] += 1;

                    // 第j列
                    if (columns[j][index] > 0) {
                        return false;
                    }
                    columns[j][index] += 1;

                    // 第k个九宫格
                    int k = getGridIndex(i, j);
                    if (nineGrids[k][index] > 0) {
                        return false;
                    }
                    nineGrids[k][index] += 1;
                }
            }
            return true;
        }


        /**
         * 获取第几个九宫格  [0-8]
         * 0 1 2
         * 3 4 5
         * 6 7 8
         */
        private int getGridIndex(int i, int j) {
            int a = i / 3;
            int b = j / 3;
            return a * 3 + b;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new P36ValidSudoku().new Solution();
        char[][] ch = new char[][] {
            {
                '5', '3', '.', '.', '7', '.', '.', '.', '.'
            },
            {
                '6', '.', '.', '1', '8', '5', '.', '.', '.'
            },
            {
                '.', '9', '8', '.', '1', '.', '.', '6', '.'
            },
            {
                '8', '.', '.', '.', '6', '.', '.', '.', '3'
            },
            {
                '4', '.', '.', '8', '.', '3', '.', '.', '1'
            },
            {
                '7', '.', '.', '.', '2', '.', '.', '.', '6'
            },
            {
                '.', '6', '.', '.', '.', '.', '2', '8', '.'
            },
            {
                '.', '.', '.', '4', '1', '9', '.', '.', '5'
            },
            {
                '.', '.', '.', '.', '8', '.', '.', '7', '9'
            }
        };
        System.out.println(solution.isValidSudoku(ch));
        // TO TEST
    }

}